import copy

class dynamic_programming:

    def __init__(self):
        self.dp = []
        self.value = []
        self.n=3


    def prepare(self):
        # 初始化dp和权值矩阵value
        Max = 1000
        temp = []
        tmp = []
        for i in range(Max):
            for j in range(Max):
                temp.append(0x7ffff)
                tmp.append(0)
            # print(temp)
            self.dp.append(copy.deepcopy(temp))
            self.value.append(copy.deepcopy(tmp))
            temp.clear()
            tmp.clear()

        self.value[0][1] = self.value[1][0] = 2
        self.value[0][2] = self.value[2][0] = 5
        self.value[0][3] = self.value[3][0] = 7
        self.value[1][2] = self.value[2][1] = 8
        self.value[1][3] = self.value[3][1] = 3
        self.value[2][3] = self.value[3][2] = 1


    # 动态规划求解旅行商问题
    '''
    dp[0][{1,2,3}] = min{l[0][1]+dp[1][{2,3}] ，l[0][2]+dp[2][{1,3}] ，l[0][3]+dp[3][{1,2}]}
    dp[1][{2,3}] = min{ l[1][2]+dp[2][{3}] ，l[1][3]+dp[3][{2}]}
    dp[2][{3}] = l[2][3]+dp[3][{}] = l[2][3]+ l[3][0]
    '''


    def dp_method(self):
        # 初始化dp数组第一列
        for i in range(self.n):
            self.dp[i][0] = self.value[i][0]
        col = 1 << self.n - 1
        print(col)
        for j in range(1, col):
            for i in range(self.n):
                # i为走过的城市，如果j中包含该城市，就跳过
                if i != 0 and j >> (i - 1) & 1:
                    continue
                '''
                从2出发，要去{1,3}。
                先看去1的路，去了1集合{1,3}中只剩下{3} ,{3}对应4,所以要求的dp表就是dp[1][4],这个4可以通过(101) ^ (1)得到,(1) = 1<<(1-1)
                再看去2的路，5 = 101的第二位是0，所以不能去2。判断第二位为1，用(5>>(2-1)) &1==1。而且也由于从2出发，就更不能去了。
                最后看去3的路，去了3集合{1,3}中只剩下{1},{1}对应这1，所以要求的dp表就是dp[3][1],1通过(101) ^ (100)得到。(100) = 1<<(3-1)
                '''
                for k in range(1, col):
                    # 判断是否要经过k城市，不能经过就跳过
                    if j >> (k - 1) & 1 == 0:
                        continue
                    if self.dp[i][j] > self.value[i][k] + self.dp[k][j ^ (1 << (k - 1))]:
                        self.dp[i][j] = self.value[i][k] + self.dp[k][j ^ (1 << (k - 1))]


if __name__ == '__main__':
    a=dynamic_programming()
    a.prepare()
    a.dp_method()